package com.递归;



import java.lang.reflect.Array;
import java.util.*;

/**
 * 罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
 *
 * 字符          数值
 * I             1
 * V             5
 * X             10
 * L             50
 * C             100
 * D             500
 * M             1000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/integer-to-roman
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 整数转罗马数字 {
    static class Solution {
        /**
         * 1.map集合罗马字符串 2.任何map的keyset
         * 3.将参数各位上的数转换出来,对应到keyset上
         * 4.将特殊的数字写好规则 ，最后将得到的字符拼接起来。
         * @param num
         * @return
         */
        public String intToRoman(int num) {
            // 把阿拉伯数字与罗马数字可能出现的所有情况和对应关系，放在两个数组中
            // 并且按照阿拉伯数字的大小降序排列，这是贪心选择思想
            int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
            String[] romans = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

            StringBuilder stringBuilder = new StringBuilder();
            int index = 0;
            while (index < 13) {
                // 特别注意：这里是等号
                while (num >= nums[index]) {
                    // 注意：这里是等于号，表示尽量使用大的"面值"
                    stringBuilder.append(romans[index]);
                    num -= nums[index];
                }
                index++;
            }
            return stringBuilder.toString();
        }

        /**
         * 字符          数值
         * I             1
         * V             5
         * X             10
         * L             50
         * C             100
         * D             500
         * M             1000
         */
        public String intToRoman2(int num) {
            String[] Q = {"","M","MM","MMM"};
            String[] B ={"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"};
            String[] S ={"","X","XX","XXX","XL","L","LX","LXX","LXXX","XC"};
            String[] G = {"","I","II","III","IV","V","VI","VII","VIII","IX"};

           return Q[num/1000]+B[num/100%10]+S[num/10%10]+G[num%10];
        }


    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.intToRoman(99999));
       // System.out.println(solution.intToRoman2(3999));


    }
}
